package com.zklh.leetcode.other.problem15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    public static void main(String[] args){
        Solution solution = new Solution();
        List<List<Integer>> result = solution.threeSum(new int[]{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6});
        for (List<Integer> integers : result) {
            for (Integer integer : integers) {
                System.out.print(integer);
            }
            System.out.println();
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {

        // 存储返回结果
        List<List<Integer>> resultLists = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return resultLists;
        }

        // 对数组进行排序
        Arrays.sort(nums);
        // 表示全为正数或者负数的情况
        if(nums[0] > 0 || nums[nums.length-1] < 0){
            return resultLists;
        }

        // 返回分界线的索引
        int midIndex = findMidIndex(nums);
        // 如果中间值为0, 则进入该步骤
        if(nums[midIndex] == 0){
            // 0的个数
            int zeroLen = 0;
            // 用于指向值为0的位置,
            int zeroIndex = midIndex;
            // 大于0数组的起始位置
            int greaterLeft = 0;
            // 获取数组中值为0的数目, 并且获取到greaterArr的起始位置
            while(zeroIndex < nums.length){
                if(nums[zeroIndex] == 0){
                    zeroIndex++;
                    zeroLen++;
                }else{
                    break;
                }
            }
            greaterLeft = zeroIndex;
            /* 分三种情况处理数组 */
            // 第一种, 一个大于0,两个小于0
            twoToOne(nums,midIndex-1,greaterLeft,resultLists);
            // 第二种, 一个小于0,一个大于0,一个等于0
            oneToOne(nums,midIndex-1,greaterLeft,resultLists);
            // 如果0的数目大于等于3,表示可以有0,0,0满足条件
            if(zeroLen >= 3){
                addResult(resultLists,0,0,0);
            }
            // 第三种, 一个小于0,两个大于0
            oneToTwo(nums,midIndex-1,greaterLeft,resultLists);

        }else{// 如果分界线值不是0, 则进入以下步骤
            int greaterLeft = midIndex;
            /* 分两种情况处理数组 */
            // 第二种, 一个大于0,两个小于0
            twoToOne(nums,midIndex-1,greaterLeft,resultLists);
            // 第三种, 一个小于0,两个大于0
            oneToTwo(nums,midIndex-1,greaterLeft,resultLists);
        }

        return resultLists;
    }


    /**
     * 返回有效数组的长度
     * @param nums
     * @return
     */
    private int rejectThree(int[] nums){
        // 中间值索引, 默认是无效索引-1;
        int midIndex = -1;
        // 表示当前有效值应该存的位置
        int valueIndex = 1;
        // 定义相同值出现的次数, 默认是1
        int repeatTime = 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[i-1]){ // 如果和上个值相同,
                repeatTime++;
            }else{ // 如果不相等, 则重置repeatTime
                repeatTime = 1;
            }
            if(repeatTime == 3){// 如果相等, 表示当前值无效, 不进行保存,valueIndex不变
                // 剔除一个后, 就将重复次数变为2
                repeatTime = 2;
            }else{ // 如果不想等, 表示当前值应该被保存, 并将
                nums[valueIndex++] = nums[i];
            }
        }
        return midIndex;
    }

    /**
     * 传入排好序的数组, 返回第一个值为0的位置, 如果没有为0,则返回第一个大于0的数
     * @param nums
     * @return
     */
    private int findMidIndex(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] >= 0){
                return i;
            }
        }
        return -1;
    }


    /**
     * 寻找小于0数组中有一个, 大于0数组中有一个值,一值为0的所有情况
     * @param nums
     * @param lessRight
     * @param greaterLeft
     */
    private void oneToOne(int[] nums,int lessRight,int greaterLeft,List<List<Integer>> result){
        int lessLeft = 0;
        int greaterRight = nums.length-1;
        while (lessLeft <= lessRight && greaterRight >= greaterLeft){
            if(-nums[lessLeft] == nums[greaterRight]){ // 如果相等, 则存入结果集
                addResult(result,nums[lessLeft],nums[greaterRight]);
                // 左边数组向右移动
                lessLeft = move(nums,lessLeft,1);
                // 右边数组向左移动
                greaterRight = move(nums,greaterRight,-1);
            }else if(-nums[lessLeft] > nums[greaterRight]){ // 当前情况左边数组左指针往右移动
                lessLeft = move(nums,lessLeft,1);
            }else{ // 右边数组右指针向左移动
                greaterRight = move(nums,greaterRight,-1);
            }


        }
    }

    /**
     * 寻找小于0的数组中有一个,大于0的数组中有两个值的情况
     * @param nums
     * @param lessRight
     * @param greaterLeft
     * @param result
     */
    private void oneToTwo(int[] nums, int lessRight, int greaterLeft, List<List<Integer>> result){
        int lessLeft = 0;
        int greaterRight = nums.length-1;
        int greaterLeftBk = greaterLeft;
        int greaterRightBk = greaterRight;
        while(lessLeft <= lessRight){
            while(greaterLeft < greaterRight){
                // 如果相等, 表示相加为0,移动右边数组两个指针
                if(-nums[lessLeft]==nums[greaterLeft]+nums[greaterRight]){
                    addResult(result,nums[lessLeft],nums[greaterLeft],nums[greaterRight]);
                    //左指针右移
                    greaterLeft = move(nums,greaterLeft,1);
                    // 右指针左移
                    greaterRight = move(nums,greaterRight,-1);
                }else if(-nums[lessLeft]>nums[greaterLeft]+nums[greaterRight]){ // 如果负数较大,移动右边数组左指针
                    greaterLeft = move(nums,greaterLeft,1);
                }else{
                    greaterRight = move(nums,greaterRight,-1);
                }
            }
            // 进行一轮后重置greaterArr左右边界
            greaterLeft = greaterLeftBk;
            greaterRight = greaterRightBk;
            lessLeft = move(nums,lessLeft,1);
        }
    }

    /**
     * 寻找大于0数组中有一个, 小于0数组中有两个值的情况
     * @param nums
     * @param lessRight
     * @param greaterLeft
     * @param result
     */
    private void twoToOne(int[] nums, int lessRight, int greaterLeft,List<List<Integer>> result){
        int lessLeft = 0;
        int greaterRight = nums.length-1;
        int lessRightBk = lessRight;
        int lessLeftBk = lessLeft;
        while(greaterLeft <= greaterRight){
            while(lessLeft < lessRight){
                if(-nums[lessLeft]-nums[lessRight] == nums[greaterRight]){
                    addResult(result,nums[lessLeft],nums[lessRight],nums[greaterRight]);
                    lessLeft=move(nums,lessLeft,1);
                    lessRight=move(nums,lessRight,-1);
                }else if(-nums[lessLeft]-nums[lessRight] > nums[greaterRight]){
                    lessLeft=move(nums,lessLeft,1);
                }else{
                    lessRight=move(nums,lessRight,-1);
                }
            }
            // 重置lessArr的左右边界
            lessRight = lessRightBk;
            lessLeft = lessLeftBk;
            greaterRight = move(nums,greaterRight,-1);
        }
    }

    private void addResult(List<List<Integer>> result,int num1, int num2, int num3){
        List<Integer> list = new ArrayList<>();
        result.add(list);
        list.add(num1);
        list.add(num2);
        list.add(num3);
    }

    /**
     * 移动, 该方法是当下个数和当前数相等的时候就一直移动, 直到不想等为止,
     * 返回移动结束时的索引
     * @param nums
     * @param index
     * @param direction 方向, 可以为-1,和+1
     * @return
     */
    private int move(int nums[], int index, int direction){
        if(direction != -1 && direction != 1){
            direction /= direction;
        }
        // 当相邻的两个数相等的时候, 就一直移动, 直到不想等, 或到终点
        while(index+direction>=0 && index+direction<nums.length && nums[index]==nums[index+direction]){
            index = index + direction;
        }
        return index+direction;
    }

    private void addResult(List<List<Integer>> result, int num1, int num2){
        addResult(result,num1,0,num2);
    }
}
